C1. Magnitude (Easy Version)
给你一个长度为
- 选项
:将 设为 。 - 选项
:将 设为 。
设上述步骤后
官方题解:
我们只需要选择一次
因为我们只需要使用一次选项
即在 前缀和最小的位置且那个位置小于 0
使用操作 2,如果多次使用了操作 2 会导致反而变小。
#define int long long
void solve() {
int n;cin >> n;
vector<int> a(n + 1), pre(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
for (int i = 1;i <= n;i++)pre[i] = pre[i - 1] + a[i];
int ans = pre[n];
for (int i = 1;i <= n;i++) {
if (pre[i] < 0) {
ans = max(ans, pre[n] - 2 * pre[i]);
}
}
cout << ans << '\n';
}
设
只需要维护最大值和最小值即可。
当前的最大值要么就是前
最小值则是前
void solve() {
int n;cin >> n;
vector<int> a(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
vector<array<int, 2>> f(n + 1);
for (int i = 1;i <= n;i++) {
f[i][0] = max(abs(f[i - 1][1] + a[i]), abs(f[i - 1][0] + a[i]));
f[i][1] = f[i - 1][1] + a[i];
}
cout << max(f[n][1], f[n][0]) << '\n';
}